Search Results

Documents authored by Betmbe, Sévérine Fetgo

Document
DOI: 10.4230/LIPIcs.CP.2023.20
Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density

Authors: Roger Kameugne, Sévérine Fetgo Betmbe, Thierry Noulamo, and Clémentin Tayou Djamegni

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
In this paper, we propose an enhancement of the filtering power of the edge finding rule, based on the Profile and the TimeTable data structures. The minimal slack and the maximum density criteria are used to select potential task intervals for the edge finding rule. The strong detection rule of the horizontally elastic edge finder of Fetgo and Tayou is then applied on those intervals, which results in a new filtering rule, named Slack-Density Horizontally Elastic Edge Finder. The new rule subsumes the edge finding rule and it is not comparable to the Gingras and Quimper horizontally elastic edge finder rule and the TimeTable edge finder rule. A two-phase filtering algorithm of complexity 𝒪(n²) (where n is the number of tasks sharing the resource) is proposed for the new rule. Improvements based on the TimeTable are obtained by considering fix part of external tasks which overlap with the potential task intervals. The detection and the adjustment of the improve algorithm are further increased, while the algorithm remains quadratic. Experimental results, on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems, show that the propounded algorithms are competitive with the state-of-the-art algorithms, in terms of running time and tree search reduction.
Cite as

Roger Kameugne, Sévérine Fetgo Betmbe, Thierry Noulamo, and Clémentin Tayou Djamegni. Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kameugne_et_al:LIPIcs.CP.2023.20,
  author =	{Kameugne, Roger and Betmbe, S\'{e}v\'{e}rine Fetgo and Noulamo, Thierry and Djamegni, Cl\'{e}mentin Tayou},
  title =	{{Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.20},
  URN =		{urn:nbn:de:0030-drops-190574},
  doi =		{10.4230/LIPIcs.CP.2023.20},
  annote =	{Keywords: Horizontally Elastic Scheduling, Edge Finder Rule, Profile, TimeTable, Resource-Constrained Project Scheduling Problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact